翻訳と辞書 Words near each other ・ S25 (ZVV) ・ S26 ・ S26 (Berlin) ・ S2600 ・ S27 ・ S27 (Munich) ・ S28 ・ S28 (Rhine-Ruhr S-Bahn) ・ S29 ・ S29 (ZVV) ・ S2C reactor ・ S2G reactor ・ S2n ・ S2o design and engineering ・ S2P ・ S2P (complexity) ・ S2S ・ S2S Pte. Ltd. ・ S2TC ・ S2W reactor ・ S2Wa reactor ・ S3 ・ S3 (classification) ・ S3 (missile) ・ S3 (Munich) ・ S3 (Nuremberg) ・ S3 (programming language) ・ S3 (Rhine-Main S-Bahn) ・ S3 (Rhine-Ruhr S-Bahn) ・ S3 (ZVV) Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク S2P (complexity) ： ウィキペディア英語版 S2P (complexity) In computational complexity theory, S is a complexity class, intermediate between the first and second levels of the polynomial hierarchy. A language $L$ is in $S\_2^P$ if there exists a polynomial-time predicate ''P'' such that * If $x\; \backslash in\; L$, then there exists a ''y'' such that for all ''z'', $P(x,y,z)=1$, * If $x\; \backslash notin\; L$, then there exists a ''z'' such that for all ''y'', $P(x,y,z)=0$, where size of ''y'' and ''z'' must be polynomial of ''x''. ==Relationship to other complexity classes== It is immediate from the definition that S is closed under unions, intersections, and complements. Comparing the definition with that of $\backslash Sigma\_^P$ and $\backslash Pi\_^P$, it also follows immediately that S is contained in $\backslash Sigma\_^P\; \backslash cap\; \backslash Pi\_^P$. This inclusion can in fact be strengthened to ZPPNP.〔 | url = http://pages.cs.wisc.edu/~jyc/papers/S2-j.pdf | volume = 73 | year = 2007}}. A preliminary version of this paper appeared earlier, in FOCS 2001, , , .〕 Every language in NP also belongs to For by definition, a language ''L'' is in NP, if and only if there exists a polynomial-time verifier ''V''(''x'',''y''), such that for every ''x'' in ''L'' there exists ''y'' for which ''V'' answers true, and such that for every ''x'' not in ''L'', ''V'' always answers false. But such a verifier can easily be transformed into an predicate ''P''(''x'',''y'',''z'') for the same language that ignores ''z'' and otherwise behaves the same as ''V''. By the same token, co-NP belongs to These straightforward inclusions can be strengthened to show that the class contains MA (by a generalization of the Sipser–Lautemann theorem) and $\backslash Delta\_^P$ (more generally, $P^=S\_2^P$). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「S2P (complexity)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.